/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.vijos;

import java.util.Arrays;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/4/18
 */
//纪念品分组
//    根据价格进行分组
//    每组最多只能包括两件纪念
//    每组纪念品的价格之和不能超过一个给定的整数
//    希望分组的数目最少
public class P4_2_1409 {

    public static int test(int limitPrice, int[] price) {
        dataVerify(limitPrice, price);
        Arrays.sort(price);
        int fz = 0;
        int leftIndex = 0;
        int rightIndex = price.length - 1;
        while (leftIndex <= rightIndex) {
            if (rightIndex > limitPrice) {
                rightIndex--;
            } else {
                if (price[leftIndex] + price[rightIndex] > limitPrice) {
                    rightIndex--;
                } else {
                    rightIndex--;
                    leftIndex++;
                }
                fz++;
            }
        }
        return fz;
    }

    private static void dataVerify(int limitPrice, int[] price) {
        for (int i = 0; i < price.length; i++) {
            if (price[i] > limitPrice) {
                throw new RuntimeException("单品价格已经超过限制价格,单品价格：" + price[i] + ",限制价格：" + limitPrice);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(test(100, new int[] {90
                ,20
                ,20
                ,30
                ,50
                ,60
                ,70
                ,80
                ,90}));
    }
}
